package org.sunny.sort;

import org.sunny.tools.Integers;

/**
 * 选择排序
 *  优于冒泡排序, 冒泡每次遇到比自己大的元素都会进行交换
 *  选择排序只会先记录比自己大的元素的下标, 一轮完毕之后才会交换
 *
 * @author Sunny
 * @date 2020/8/20
 */
public class SelectionSort {

    public static void main(String[] args) {
        Integer[] arr = Integers.random(1000, 1, 100);
        selectionSort(arr);
        System.out.println(Integers.isAscOrder(arr));
    }

    /**
     * 选择排序
     *  记录最大值的索引, 将其与数组最后一个元素交换位置
     *
     * @param arr 待排序数组
     * @author Sunny
     * @date 2020/8/20
     */
    public static void selectionSort(Integer[] arr) {
        for (int end = arr.length - 1; end > 0; end--) {

            //记录最大值的下标
            int maxIndex = 0;
            for (int begin = 1; begin < end; begin++) {
                //为了达到稳定性, 这里要包含等于的情况,如果后面有与最大值相等的,将后面索引对应的元素作为最大值替换到最后
                if (SortUtils.cmp(arr[maxIndex], arr[begin]) <= 0) {
                    maxIndex = begin;
                }
            }
            //交换数据
            SortUtils.swap(arr, maxIndex, end);
        }
    }
}
